HW#1 --- last modified March 02 2019 21:25:06..

Solution set.

Due date: Feb 6

Files to be submitted:
  Hw1.tex
  Random.zip

Purpose: To learn about random number generators, using indicator random variables, and generating random permutations

Specification:

For the written part of the homework do problems 5.1-2, 5.1-3, 5.2-4, and 5.4-2 out of CLRS and submit these in the file Hw1.tex

For the programming part of the assignment, you will first create a Java interface called Coin. This interface should consist of one public method flip() which returns a boolean. You will then create subclasses of Coin: FileCoin, PrimeCoin, and UnbiasedCoin.

The FileCoin has a constructor which takes a String argument which is supposed to be the filename of a file in which is stored a random sequence of bits. The constructor should initialize an offset integer variable to 0. Each time flip is called it return the offset valued bit (not byte) from the file where 1 is true and 0 is false. it then bumps offset. You might be able to obtain test files from a site like random.org or if you are feeling silly NoEntropy.net.

The idea for PrimeCoin is based on a very inefficient not so random number generator I thought of when I was an undergrad. PrimeCoin has a contructor which take an integer n. It then stores the integer 2*n+1 in some field currentValue (so what's stored is an odd number). When flip() is called you check if currentValue is a prime or not, if it is you output true; otherwise, you output false. Later in the semester we will learn efficient ways to check for primality, but for this homework you can do a brute force check. flip() should then add 2 to the currentValue. Notice, this coin will be somewhat biased. You can look up facts about the density of primes, such as the prime number theorem, Bertrand's Postulate, or Sylvester's theorem to try to figure out how biased it can be.

UnbiasedCoin's constructor should take as its argument a Coin. Its flip() method should make calls to this coin to implement an unbiased Coin flip. You should use the algorithm you came up with for your solution to problem 5.1-3 to code this. Note the solution to 5.1-3 assumes one has a constant bias. In the case of PrimeCoin the bias increases with n. Two bonus points are available if you give a good write up on to what degree this needs to be compensated for if we want the algorithm to really work for PrimeCoin and how to modify it in this case.

Now that you have an unbiased coin, you should make a class RandomRange. This class should take an UnbiasedCoin in its constructor and well as two integer arguments: low and high. RandomRange should have one public method value() which returns a random integer between low and high that is gotten by using the UnbiasedCoin's flip method according to your solution to 5.1-2.

Next you will create an interface RandomPermutation which has a public method getPermutation which returns a List and takes as arguments an integer n. This functions is supposed to return as a List a random permutation of the integer 1,2,... n. You will make two implementation subclasses of this class SortingPermutation and InPlacePermutation. The former implements getPermutation(n) using the Permute-by-Sorting algorithm from the book. The latter implements getPermutation(n) using the Randomize-In-Place algorithm from the book. Each of these implementation should have a constructor which takes a UnbiasedCoin object that will be used for the randomization. Recall the reason why we're interested being able to generate random permutations is because we want to be able to guarantee the expected run-time of certain algorithms such as the hire assistant algorithm talked about in class.

As a last thing for this assignment, you should write a driver class TestPermutation which will be run on the command line with a line like:

java TestPermutation Name_of_Coin(args) Name_of_RandomPermutation size_of_permutation number_to_output

The UnbiasedCoin used by RandomRange and hence by either SortingPermutation or InPlacePermutation should be given by Name_of_Coin. Some examples of how this might look are:

java TestPermutation FileCoin("some.txt") SortingPermutation 20 30

java TestPermutation PrimeCoin(100) InPlacePermutation 50 10

The output should be number_to_ouput many lines where each line contains the pretty printed result of a called to getPermutation(size_of_permutation). For instance, java TestPermutation PrimeCoin(100) InPlacePermutation 2 6 might return:

(2,1)
(2,1)
(1,2)
(2,1)
(1,2)
(2,1)

When you are ready to submit, ZIP up all your files and submit them in Random.zip.

Point Breakdown